//给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，打印节点数值总和等于某个给定值的所有路径的数量。注意，路径不一定非得从二叉树的
//根节点或叶节点开始或结束，但是其方向必须向下(只能从父节点指向子节点方向)。 
//
// 示例： 给定如下二叉树，以及目标和 sum = 22， 
//
// 
//              5
//             / \
//            4   8
//           /   / \
//          11  13  4
//         /  \    / \
//        7    2  5   1
// 
//
// 输出： 
//
// 
//3
//解释：和为 22 的路径有：[5,4,11,2], [5,8,4,5], [4,11,7] 
//
// 提示： 
//
// 
// 节点总数 <= 10000 
// 
//
// Related Topics 树 深度优先搜索 二叉树 👍 148 👎 0


package LeetCode.editor.cn;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ldltd
 * @date 2025-07-17 00:09:58
 * @description 面试题 04.12.求和路径
 */
public class PathsWithSumLcci {
    public static void main(String[] args) {
        //测试代码
        PathsWithSumLcci fun = new PathsWithSumLcci();
        Solution solution = fun.new Solution();

    }

//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)

    //  Definition for a binary tree node.
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
        // 朴素解法，dfs遍历每个节点作为起点，然后再dfs遍历每个节点的所有路径
        // 时间复杂度O(n^2)，空间复杂度O(h)
        public int pathSum1(TreeNode root, int sum) {
            if (root == null) {
                return 0;
            }

            int ret = rootSum(root, sum);
            ret += pathSum1(root.left, sum);
            ret += pathSum1(root.right, sum);
            return ret;
        }

        public int rootSum(TreeNode root, int sum) {
            int ret = 0;

            if (root == null) {
                return 0;
            }
            int val = root.val;
            if (val == sum) {
                ret++;
            }

            ret += rootSum(root.left, sum - val);
            ret += rootSum(root.right, sum - val);
            return ret;

        }

        // 前缀和解法，利用哈希表记录前缀和出现的次数
        // 时间复杂度O(n)，空间复杂度O(h)

        public int pathSum(TreeNode root, int sum) {
            Map<Long, Integer> prefix = new HashMap<Long, Integer>();
            prefix.put(0L, 1);
            return dfs(root, prefix, 0, sum);
        }

        public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int sum) {
            if (root == null) {
                return 0;
            }

            int ret = 0;
            curr += root.val;
            // 找出有多少个前缀和满足 curr - prefix = sum
            ret = prefix.getOrDefault(curr - sum, 0);
            // 将当前前缀和加入哈希表
            prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
            // 继续往下遍历
            ret += dfs(root.left, prefix, curr, sum);
            ret += dfs(root.right, prefix, curr, sum);
            // 回溯，撤销当前前缀和。因为每条路径只能使用一次，所以在返回上一层时要撤销当前前缀和
            prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);

            return ret;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
